package org.example.Soution003;

import java.util.*;
import java.util.stream.Collectors;

public class PileKthRelease {
    public static void main(String[] args) {
        int[] a={-1,1,4,-4,3,5,4,-2,3,-1};
        PileKthRelease p=new PileKthRelease();
        int[] res=p.topKFrequent(a,3);
        System.out.println(Arrays.toString(res));
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        int allSize=map.size();
        Set<Map.Entry<Integer, Integer>> set=map.entrySet();
        List<Map.Entry<Integer,Integer>> list= new ArrayList<>(set);
        //先建堆
        makeHeap(list,0,allSize);
        //再找结果
        int[] res=new int[k];
        for(int i=0;i<k;i++){
            res[i]=list.get(0).getKey();
            list.set(0,list.get(allSize-1));
            maxHeap(list,0,allSize);
            allSize--;
        }
        return res;
    }

    public void makeHeap(List<Map.Entry<Integer,Integer>> list,int start,int length){
        for(int i=(length>>1)-1;i>=0;i--){
            maxHeap(list,i,length);
        }
    }

    public void maxHeap(List<Map.Entry<Integer,Integer>> list,int start,int length){
        int left=start*2+1; int right=start*2+2;   int largest=start;
        if(left<length&&list.get(left).getValue()>list.get(largest).getValue()){
            largest=left;
        }
        if(right<length&&list.get(right).getValue()>list.get(largest).getValue()){
            largest=right;
        }
        if(largest!=start){
            swap(list,start,largest);
            maxHeap(list,largest,length);
        }
    }

    public void swap(List<Map.Entry<Integer,Integer>> list,int i,int j){
        Map.Entry<Integer,Integer> tempMap=list.get(i);
        list.set(i,list.get(j));
        list.set(j,tempMap);
    }
}
